#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct element{
    char * data;
    struct element * prev;
    struct element * next;
};
struct element *  create_element(char * data){
    struct element * elem=(struct element *)malloc(sizeof(struct element));
    int data_len=strlen(data)+1;
    elem->data=(char *)malloc(sizeof(char)*data_len);
    strcpy(elem->data,data);
    elem->prev=NULL;
    elem->next=NULL;
    return elem;
};
void print_element(struct element * elem){
    if(elem==NULL) 
        return ;
    else if(elem->data==NULL) 
        printf("data:NULL \t prev:%p \t next:%p\n",elem->prev,elem->next);
    else
        printf("data:%s \t prev:%p \t next:%p\n",elem->data,elem->prev,elem->next);

}

struct double_linked_list{
    struct element * head;
    struct element * tail;
};
struct double_linked_list * create_double_linked_list(struct element * elem){
    struct double_linked_list * lst=(struct double_linked_list *)malloc(sizeof(struct double_linked_list));
    lst->head=elem;
    lst->tail=elem;
    lst->head->next=lst->tail;
    lst->tail->prev=lst->head;
    return lst;
}
void append_tail_double_linked_list(struct double_linked_list * lst,struct element * elem){
    lst->tail->next=elem;
    elem->prev=lst->tail;
    lst->tail=elem;
    lst->tail->next=lst->head;
    lst->head->prev=lst->tail;
}

void append_head_double_linked_list(struct double_linked_list * lst,struct element * elem){
    lst->head->prev=elem;
    elem->next=lst->head;
    lst->head=elem;
    lst->tail->next=lst->head;
    lst->head->prev=lst->tail;
}
void print_list(struct double_linked_list * lst){
    if(lst==NULL) return;
    if(lst->head==NULL) return;
    struct element * current=lst->head;
    do{
        print_element(current);
        if(current==NULL) return;
        current=current->next;
    }while(current!=lst->head);
}   


void insert_double_linked_list(struct double_linked_list * lst,int index,struct element * elem){
    if(lst==NULL) return;
    if(lst->head==NULL) return;
    if(index==0) {
        append_head_double_linked_list(lst,elem);
        return ;
    }else{
        int i=0;
        struct element * current=lst->head;
        int status=0;
        while(current->next!=lst->head){
            current=current->next;
            i++;
            if((index-1)==i) {
                status=1;
                break;
            }
        }
        if(status==1){
            struct element * prev=current;
            struct element * next=current->next;
            elem->next=next;
            next->prev=elem;

            elem->prev=prev;
            prev->next=elem;

        }else{
            printf("index out of range\n");
            return ;
        }
    }
}

int search_data(struct double_linked_list * lst,char * data){
    int index=-1;
    if(lst==NULL) return index;
    else if(lst->head==NULL) return index;
    struct element * current_node=lst->head;
    int tmp=-1;
    do{
        tmp++;
        if(strcmp(current_node->data,data)==0){
            index=tmp;
            break;
        };
        current_node=current_node->next;
    }while(current_node!=lst->head);
    return index;
}

char * search_index(struct double_linked_list * lst,int index){
    if(index<0) return NULL;
    int tmp=0;
    struct element * current_node=lst->head;
    do{
        if(tmp==index)  return current_node->data;
        current_node=current_node->next;
        tmp++;
    }while(current_node!=lst->head);
    return NULL;
}

void delete_element(struct element * elem){
    if(elem==NULL) return ;
    if(elem->data!=NULL) free(elem->data);
    elem->data=NULL;
    elem->next=NULL;
    elem->prev=NULL;
    free(elem);
    elem=NULL;
    return ;
}

int  remove_data(struct double_linked_list * lst,char * data){
    if(lst==NULL) return -1;
    else if(lst->head==NULL) return -1;
    struct element * current_node=lst->head;
    struct element * previous_node;
    struct element * next_node;
    do{
        if(strcmp(current_node->data,data)==0){
            previous_node=current_node->prev;
            next_node=current_node->next;
            if((previous_node==next_node)&&(next_node==current_node)){
                delete_element(current_node);
                lst->head=NULL;
                lst->tail=NULL;
                return -1;
            }
            previous_node->next=next_node;
            next_node->prev=previous_node;
            if(current_node==lst->head){
                lst->head=next_node;
                lst->tail->next=lst->head;
            }else if(current_node==lst->tail){
                lst->tail=previous_node;
                lst->head->prev=lst->tail;
            }
            delete_element(current_node);
            return 0;
        }
        current_node=current_node->next;
    }while(current_node!=lst->head);
    return -1;
}

int remove_index(struct double_linked_list * lst,int index){
    if(lst==NULL) return -1;
    else if(lst->head==NULL) return -1;
    else if(index<0) return -1;
    int tmp=0;
    struct element * current_node=lst->head;
    struct element * prev_node, * next_node;
    do{
        if(tmp==index){
            next_node=current_node->next;
            prev_node=current_node->prev;
            if((current_node==prev_node)&&(current_node==next_node)){
                delete_element(current_node);
                lst->head=NULL;
                lst->tail=NULL;
                return 0;
            }
            prev_node->next=next_node;
            next_node->prev=prev_node;
            //如果前一个是尾部，那么他就是头
            if(current_node->prev==lst->tail)lst->head=next_node;
            if(current_node->next==lst->head)lst->tail=prev_node;
            delete_element(current_node);
            return 0;
        }
        current_node=current_node->next;
        tmp++;
    }while(current_node!=lst->head);
    return -1;
}

int remove_head(struct double_linked_list * lst){
    if(lst==NULL) return -1;
    else if(lst->head==NULL) return -1;
    else if(lst->head==lst->tail){
        struct element * current_node=lst->head;
        lst->head=NULL;
        lst->tail=NULL;
        delete_element(current_node);
        current_node=NULL;
        return 0;
    }else{
        struct element * current_node=lst->head;
        struct element * previous_node=current_node->prev;
        struct element * next_node=current_node->next;
        next_node->prev=previous_node;
        previous_node->next=next_node;
        lst->head=next_node;
        lst->tail->prev=lst->head;
        delete_element(current_node);
        return 0;
    }
}

int remove_tail(struct double_linked_list * lst){
    if(lst==NULL) return -1;
    else if(lst->head==NULL) return -1;
    else if(lst->head==lst->tail){
        struct element * current_node=lst->head;
        lst->head=NULL;
        lst->tail=NULL;
        delete_element(current_node);
        current_node=NULL;
        return 0;        
    }else{
        struct element * current_node=lst->tail;
        struct element * previous_node=current_node->prev;
        struct element * next_node=current_node->next;   
        next_node->prev=previous_node;
        previous_node->next=next_node;  
        lst->tail=previous_node;   
        lst->head->prev=lst->tail;
    }
}


int main(){
    char data[20]={0};
    scanf("%s",data);
    struct element * head=create_element(data);
    print_element(head);
    struct double_linked_list * lst=create_double_linked_list(head);
    for(int i=0;i<4;i++){
        scanf("%s",data);
        struct element * elem=create_element(data);
        print_element(elem);
        append_head_double_linked_list(lst,elem);
    }
    print_list(lst);
    struct element * elem=create_element(data);
    print_element(elem);    
    insert_double_linked_list(lst,6,elem);
    print_list(lst);

    for(int i=0;i<4;i++){
        scanf("%s",data);
        printf("search_index:%d\n",search_data(lst,data));
    }
    
    for(int i=0;i<4;i++){
        int index=-1;
        scanf("%d",&index);
        printf("search_data:%s\n",search_index(lst,index));
    }

    print_list(lst);
    int index;
    
    for(int i=0;i<5;i++){
    
        printf("remove head\n");
        remove_index(lst,index);
        print_list(lst);
    }     
    return 0;
}